// MaxHistogram.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <stack>
using namespace std;

//Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.


//Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

//The largest rectangle is shown in the shaded area, which has area = 10 unit.



int largestRectArea(vector<int> &h) {
    stack<int> p;
    int i = 0, m = 0;
    h.push_back(0);
    while(i < h.size()) {
        if(p.empty() || h[p.top()] <= h[i])
            p.push(i++);
        else {
            int t = p.top();
            p.pop();
            m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
        }
    }
    return m;
}


//solution 2:

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int num = height.size();
        if(num == 0) return 0;
        if(num == 1) return height[0];
        
        stack<int> S; int area[num];
        
        for(int i = 0; i<num; i++)
        {
            while(!S.empty())
            {
                if(height[S.top()] >= height[i])
                    S.pop();
                else
                    break;
            }
            
            if(S.empty())
                area[i] = i;
            else
                area[i] = i-S.top() -1;
            
            S.push(i);
        }
        
        while(!S.empty())
            S.pop();
        
        for(int i = num-1; i>=0; i--)
        {
            while(!S.empty())
            {
                if(height[S.top()] >= height[i])
                    S.pop();
                else
                    break;
            }
            
            if(S.empty())
                area[i] += num-i-1;
            else
                area[i] += S.top() - i-1;
                
            S.push(i);
        }
        
        int maxArea = 0;
        for(int i = 0; i<num; i++)
        {
            int nArea = (area[i]+1)*height[i];
            maxArea=max(maxArea, nArea);
        }
        
        return maxArea;
        return 0;
        
    }
};

int _tmain(int argc, _TCHAR* argv[])
{

	vector<int> testCase;
	testCase.push_back(2);
	testCase.push_back(1);
	testCase.push_back(1);
	testCase.push_back(4);


	int nRet = largestRectArea(testCase);

	return 0;
}

